package class_2;

import java.util.Arrays;

public class Coding_quickSort3 {
	public static void quickSort(int[] arr) {
		if(arr==null || arr.length<2) {
			return ;
		}
		quick(arr,0, arr.length-1);
	}
	public static void quick(int[] arr, int l,int r) {
		//l==r, l>r直接返回， 不用处理。
		if(l>=r) {
			return ;
		}
		
		int pivot = partition(arr,l,r);
		System.out.println("partition:"+Arrays.toString(arr));
		quick(arr,l,pivot-1);
		quick(arr,pivot+1,r);
	}
	public static void swap(int[] arr,int i,int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	public static int partition(int[] arr,int l,int r) {
		int x = arr[l];
		int i = l;
		int j = r + 1;
		while(true) {
			 do {
	                j--;
	            } while (arr[j] > x);

	            do {
	                i++;
	            } while (arr[i] < x);

	            if (i < j) {
	                swap(arr, i, j);
	            } else {
	                return j;
	            }
		}
	}
	
	public static void main(String[] args) {
		int[] arr = {13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21};
		System.out.println("排序前:"+Arrays.toString(arr));
		quickSort(arr);
		System.out.println("排序后:"+Arrays.toString(arr));
	}
	
}
